package leetcode.day_2020_12_21_12_28;

import com.sun.java.swing.plaf.windows.WindowsTextAreaUI;

import java.util.*;

public class Twitter {
    private static int timestamp = 0;
    // 需要一个映射将userId和user对象对应起来
    private HashMap<Integer, User> userMap = new HashMap<>();
    private static class Tweet {
        private int id;
        private int time;
        private Tweet next;

        public Tweet(int id, int time) {
            this.id = id;
            this.time = time;
            this.next = null;
        }
    }

    private static class User {
        private int id;
        public Set<Integer> followed;
        // 用户发表的推文链接头结点
        public Tweet head;

        public User(int userId) {
            followed = new HashSet<>();
            this.id = userId;
            this.head = null;
            // 关注一下自己
            follow(id);
        }

        public void follow(int userId) {
            followed.add(userId);
        }

        public void unfollow(int userId) {
            // 不可取关自己
            if (userId != this.id) {
                followed.remove(userId);
            }
        }

        public void post(int tweetId) {
            Tweet twt = new Tweet(tweetId, timestamp);
            timestamp++;
            // 将新建的推文插入链表头
            // 越靠前的推文time值越大
            twt.next = head;
            head = twt;
        }
    }

    public Twitter () {}

    /**
     * user发表一条动态
     * @param userId
     * @param tweetId
     */
    public void postTweet(int userId, int tweetId) {
        // 若userId不存在，则新建
        if(!userMap.containsKey(userId)) {
            userMap.put(userId, new User(userId));
        }
        User u = userMap.get(userId);
        u.post(tweetId);
    }

    /**
     * follower关注followee
     * @param followerId
     * @param followeeId
     */
    public void follow(int followerId, int followeeId) {
        // 若follower不存在，则创建
        if(!userMap.containsKey(followeeId)) {
            User u = new User(followerId);
            userMap.put(followerId, u);
        }
        userMap.get(followeeId).follow(followeeId);
    }

    /**
     * follower取关followee，如果Id不存在则什么都不做
     * @param followerId
     * @param followeeId
     */
    public void unfollow(int followerId, int followeeId) {
        if(userMap.containsKey(followerId)) {
            User flwer = userMap.get(followerId);
            flwer.unfollow(followeeId);
        }
    }

    /**
     * 返回该user关注的人（包括他自己）最近的动态id
     * 最多10条，而且这些动态必须按从新到旧的时间线顺序排列
     * （合并K个有序链表，需要用到优先级队列）
     * @param userId
     * @return
     */
    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        if(!userMap.containsKey(userId)) return res;
        // 关注列表的用户id
        Set<Integer> users = userMap.get(userId).followed;
        // 自动通过time属性从大到小排序，容量为users的大小
        PriorityQueue<Tweet> pq = new PriorityQueue<>(users.size(), (a, b)->(b.time - a.time));
        // 先将所有链表头结点插入优先级队列
        for(int id : users) {
            Tweet twt = userMap.get(id).head;
            if (twt == null) continue;
            pq.add(twt);
        }
        while (!pq.isEmpty()) {
            // 最多返回10条
            if(res.size() == 10) break;
            // 弹出time值最大的（最近发表的）
            Tweet twt = pq.poll();
            res.add(twt.id);
            // 将下一篇Tweet插入进行排序
            if(twt.next != null) {
                pq.add(twt.next);
            }
        }
        return res;
     }
}
